# -*- coding: utf-8 -*-
"""
    Time    : 2020/12/30 9:25 下午
    Author  : Thinkgamer
    File    : add07-二叉树层次遍历同一层节点按行输出.py
    Desc    : 小米面试， eg:
                    A
                   / \
                  B   C
                 / \   \
                D   E   F
                输出为：
                    A
                    BC
                    DEF
"""


class ListNode:
	def __init__(self, v):
		self.val = v
		self.left = None
		self.right = None


def show(root):
	if not root:
		return
	# 层次遍历，只不过在每一层遍历时，记录一个临时的队列，保证一层的节点能够记录在一个 临时的 list 中
	queue = [root]
	result = [[root.val]]
	
	while queue:
		temp_queue = list()
		temp_result = list()
		root = queue.pop(0)
		while root:
			if root.left:
				temp_queue.append(root.left)
				temp_result.append(root.left.val)
			if root.right:
				temp_queue.append(root.right)
				temp_result.append(root.right.val)
			
			if queue:
				root = queue.pop(0)
			else:
				root = None
		if temp_result:
			result.append(temp_result)
		queue += temp_queue
	
	return result
		

if __name__ == "__main__":
	# 创建一个二叉树
	a = ListNode("A")
	b = ListNode("B")
	c = ListNode("C")
	d = ListNode("D")
	e = ListNode("E")
	f = ListNode("F")
	a.left = b
	a.right = c
	b.left = d
	b.right = e
	c.right = f
	result = show(a)
	print(result)
